package com.zhugang.week04;

import java.util.*;

/**
 * @program algorithms
 * @description: mergeIntervals
 * @author: chanzhugang
 * @create: 2022/06/30 08:58
 */
public class MergeIntervals {

    /**
     * 56. 合并区间
     * <p>
     * 总结：区间问题先排序
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 先排序， 遍历比较前一个数组右边和后一个数组左边值的大小
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        List<int[]> result = new ArrayList<>();
        int curLeft = intervals[0][0];
        int curRight = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= curRight) {
                if (intervals[i][1] > curRight) {
                    // 满足合并要求
                    curRight = intervals[i][1];
                }
            } else {
                result.add(new int[]{curLeft, curRight});
                // 不满足更新
                curLeft = intervals[i][0];
                curRight = intervals[i][1];
            }
        }
        result.add(new int[]{curLeft, curRight});
        return result.toArray(new int[result.size()][]);
    }
}